package com.acwing.partition11;

import java.io.*;
import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2021/12/26 15:21
 */
public class AC1076迷宫问题 {

    private static final int N = 1010;
    private static final int[][] maze = new int[N][N], dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    //多开一个prev数组来记录当前位置是由哪个位置到达的，prev[i][j]表示maze[i][j]的是由二元组坐标转移过来
    private static final int[][][] prev = new int[N][N][2];
    private static int n = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        n = Integer.parseInt(s[0]);
        for (int i = 0; i < n; i++) {
            s = reader.readLine().split("\\s+");
            for (int j = 0; j < n; j++) maze[i][j] = Integer.parseInt(s[j]);
        }
        //路径的记录是反向的，所以从终点往起点走
        bfs(n - 1, n - 1);
        writer.flush();
    }

    private static void bfs(int x, int y) throws IOException {
        LinkedList<int[]> queue = new LinkedList<>();
        queue.addLast(new int[]{x, y});
        for (int i = 0; i < prev.length; i++) {
            for (int j = 0; j < prev[i].length; j++) {
                prev[i][j][0] = prev[i][j][1] = -1;
            }
        }
        prev[x][y][0] = prev[x][y][1] = 0;
        while (!queue.isEmpty()) {
            int[] curr = queue.pollFirst();
            int currX = curr[0], currY = curr[1];
            if (currX == 0 && currY == 0) break;
            for (int[] dir : dirs) {
                int nextX = currX + dir[0], nextY = currY + dir[1];
                if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) continue;
                if (maze[nextX][nextY] == 1 || prev[nextX][nextY][0] != -1) continue;
                queue.addLast(new int[]{nextX, nextY});
                prev[nextX][nextY][0] = currX;
                prev[nextX][nextY][1] = currY;
            }
        }
        int[] curr = {0, 0};
        while (curr[0] != -1 && curr[1] != -1) {
            writer.write(curr[0] + " " + curr[1] + "\n");
            if (curr[0] == n - 1 && curr[1] == n - 1) break;
            curr = prev[curr[0]][curr[1]];
        }
    }
}
